The invention relates to computing systems, and more particularly, to systems and methods for improving the performance of computing systems.
Modern computing systems are often called upon to process massive amounts of data. The amount of processing that is required to handle large volumes of data may overwhelm computing systems that utilize only a single processor. As a result, many computing functions are now implemented using parallel processing.
Parallel processing refers to the concept of speeding-up the execution of computing operations by dividing the operations into multiple fragments that can execute concurrently, each on its own processor. A set of operations being executed across n processors might execute n times faster than it would using a single processor, subject to any overhead associated with parallelizing the operations.
One problem faced by systems when attempting to parallelize operations is the existence of dependencies between different sequences of operations. For example, consider a parallel processing system in which a first sequence of operations is processed by a first CPU and a second sequence of operations is processed by a second CPU. Assume that the first sequence of operations requires the value of a given variable v, but that the variable v is established by the second sequence of operations. In this circumstance, a dependency exists between the flow of the first sequence of operations and the second sequence of operations since the first sequence cannot proceed until and unless it acquires the value of variable v from the second sequence of operations.
Such dependencies negatively affect the ability of system to parallelize computing operations. When dependencies occur between sequences of operations, they may be translated into synchronization operations, and into a data communication between CPUs on a distributed parallel platform. This forces a serialization of the operations and prevents true parallel processing.
Conventional computing systems are unable to effectively handle these types of dependencies in sequences of operations. For example, consider conventional electronic design automation (EDA) tools. The electronic design process for an integrated circuit (IC) involves EDA tools used to describing and design the behavioral, architectural, functional, and structural attributes of an IC or electronic system. Despite increases in processing power for modern computing systems, EDA execution times have not kept pace with modern designs since many modern IC designs being produced by electronics companies are constantly increasing in complexity and number of transistors. Constantly improving IC manufacturing technologies create IC chips at ever-smaller feature sizes, which allow increasingly greater quantities of transistors to be placed within the same chip area with each new generation of semiconductor processing technology. One reason parallel processing of EDA tools has not been efficiently implemented is because large amounts of dependencies typically exist within any attempt to parallelize EDA operations.
Embodiments of the present invention provide an improved method and system for implementing parallel processing of computing operations by effectively handling dependencies between different sequences of computing operations. In some embodiments of the invention, some or all operations corresponding to dependencies between different sequences of operations are duplicated among the different sequences. This approach may be used to implement parallel processing of EDA tools.
Further details of aspects, objects, and advantages of the invention are described below in the detailed description, drawings, and claims. Both the foregoing general description and the following detailed description are exemplary and explanatory, and are not intended to be limiting as to the scope of the invention.